#include <iostream>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>
#include <unordered_set>

using namespace std;

/*
class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        int x_len=matrix.size();
        int y_len=matrix[0].size();
        stack<pair<int,int>> dfs;
        vector<vector<int>> res;
        vector<vector<int>> direction{{-1,0},{1,0},{0,1},{0,-1}};
        pair<int,int> pos;
        bool can_pacific=false;
        bool can_atlantic=false;
        int new_x=0;
        int new_y=0;
        vector<pair<int,int>> visited;
        for(int i=0;i<x_len;i++){
            for(int j=0;j<y_len;j++){
                can_pacific=false;
                can_atlantic=false;
                visited.clear();
                dfs.push(make_pair(i,j));
                visited.push_back(make_pair(i,j));
                //cout<<"("<<i<<","<<j<<"):"<<matrix[i][j]<<endl;
                if(i==0||j==0){
                    can_pacific=true;
                }
                if(i==x_len-1||j==y_len-1){
                    can_atlantic=true;
                }
                while(!dfs.empty()){
                    pos=dfs.top();
                    dfs.pop();
                    for(auto& dir:direction){
                        new_x=pos.first+dir[0];
                        new_y=pos.second+dir[1];
                        if(0<=new_x&&new_x<x_len&&0<=new_y&&new_y<y_len&&find(visited.begin(),visited.end(),make_pair(new_x,new_y))==visited.end()&&matrix[pos.first][pos.second]>=matrix[new_x][new_y]){
                            dfs.push(make_pair(new_x,new_y));
                            visited.push_back(make_pair(new_x,new_y));
                            //cout<<"next: "<<"("<<new_x<<","<<new_y<<"):"<<matrix[new_x][new_y]<<" ";
                            if(new_x==0||new_y==0){
                                can_pacific=true;
                            }
                            if(new_x==x_len-1||new_y==y_len-1){
                                can_atlantic=true;
                            }
                        }
                    }
                }
                if(can_atlantic&&can_pacific){
                    res.push_back({i,j});
                }
                //cout<<endl;
            }
        }
        return res;
    }
};
*/
/*
class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        int x_len=matrix.size();
        if(x_len==0){
            return matrix;
        }
        int y_len=matrix[0].size();
        vector<vector<int>> direction{{-1,0},{1,0},{0,1},{0,-1}};
        vector<vector<bool>> pacific(x_len,vector<bool>(y_len,false));
        vector<vector<bool>> atlantic(x_len,vector<bool>(y_len,false));
        stack<pair<int,int>> dfs;
        vector<vector<int>> res;
        //vector<vector<bool>> visited(x_len,vector<bool>(y_len,false));
        vector<pair<int,int>> visited;
        pair<int,int> pos;
        int new_x=0;
        int new_y=0;

        // pacific
        for(int i=0;i<x_len;i++){
            pacific[i][0]=true;
            atlantic[i][y_len-1]=true;
        }
        for(int j=0;j<y_len;j++){
            pacific[0][j]=true;
            atlantic[x_len-1][j]=true;
        }
        for(int i=0;i<x_len;i++){
            for(int j=0;j<y_len;j++){
                visited.clear();
                dfs.push(make_pair(i,j)); 
                visited.push_back(make_pair(i,j));     
                while(!dfs.empty()){
                    pos=dfs.top();
                    dfs.pop();
                    for(auto& dir:direction){
                        new_x=pos.first+dir[0];
                        new_y=pos.second+dir[1];
                        if(0<=new_x&&new_x<x_len&&0<=new_y&&new_y<y_len&&find(visited.begin(),visited.end(),make_pair(new_x,new_y))==visited.end()&&matrix[pos.first][pos.second]>=matrix[new_x][new_y]){
                            dfs.push(make_pair(new_x,new_y));
                            visited.push_back(make_pair(new_x,new_y));
                            if(pacific[new_x][new_y]){
                                pacific[pos.first][pos.second]=true;
                            }
                        }
                    }
                }
            }
        }

        for(int i=x_len-1;i>0;i--){
            for(int j=y_len-1;j>0;j--){
                visited.clear();
                dfs.push(make_pair(i,j)); 
                visited.push_back(make_pair(i,j));     
                while(!dfs.empty()){
                    pos=dfs.top();
                    dfs.pop();
                    for(auto& dir:direction){
                        new_x=pos.first+dir[0];
                        new_y=pos.second+dir[1];
                        if(0<=new_x&&new_x<x_len&&0<=new_y&&new_y<y_len&&find(visited.begin(),visited.end(),make_pair(new_x,new_y))==visited.end()&&matrix[pos.first][pos.second]>=matrix[new_x][new_y]){
                            dfs.push(make_pair(new_x,new_y));
                            visited.push_back(make_pair(new_x,new_y));
                            if(atlantic[new_x][new_y]){
                                atlantic[pos.first][pos.second]=true;
                            }
                        }
                    }
                }
            }
        }
        cout<<endl;
        for(int i=0;i<x_len;i++){
            for(int j=0;j<y_len;j++){
                cout<<pacific[i][j]<<" ";            
            }
            cout<<endl;
        }
        cout<<endl;
        for(int i=0;i<x_len;i++){
            for(int j=0;j<y_len;j++){
                cout<<atlantic[i][j]<<" ";            
            }
            cout<<endl;
        }
        cout<<endl;
        for(int i=0;i<x_len;i++){
            for(int j=0;j<y_len;j++){
                cout<<(atlantic[i][j]&&pacific[i][j])<<" ";
                if(atlantic[i][j]&&pacific[i][j]){
                    res.push_back({i,j});
                }
            }
            cout<<endl;
        }
        return res;
    }
};
*/

/*
class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        int x_len=matrix.size();
        if(x_len==0){
            return matrix;
        }
        int y_len=matrix[0].size();
        vector<vector<int>> direction{{-1,0},{1,0},{0,1},{0,-1}};
        vector<vector<bool>> pacific(x_len,vector<bool>(y_len,false));
        vector<vector<bool>> atlantic(x_len,vector<bool>(y_len,false));
        stack<pair<int,int>> dfs;
        vector<vector<int>> res;
        vector<vector<bool>> visit_a(x_len,vector<bool>(y_len,false));
        vector<vector<bool>> visit_p(x_len,vector<bool>(y_len,false));
        //vector<pair<int,int>> visited;
        pair<int,int> pos;
        int new_x=0;
        int new_y=0;

        // pacific
        for(int i=0;i<x_len;i++){
            pacific[i][0]=true;
            //visit_p[i][0]=true;
            atlantic[i][y_len-1]=true;
            //visit_a[i][y_len-1]=true;
        }
        for(int j=0;j<y_len;j++){
            pacific[0][j]=true;
            //visit_p[0][j]=true;
            atlantic[x_len-1][j]=true;
            //visit_a[x_len-1][j]=true;
        }
        //p
        for(int i=0;i<x_len;i++){
            for(int j=0;j<y_len;j++){
                if(visit_p[i][j]){
                    continue;
                }
                dfs.push(make_pair(i,j)); 
                visit_p[i][j]=true; 
                while(!dfs.empty()){
                    pos=dfs.top();
                    dfs.pop();
                    for(auto& dir:direction){
                        new_x=pos.first+dir[0];
                        new_y=pos.second+dir[1];
                        if(0<=new_x&&new_x<x_len&&0<=new_y&&new_y<y_len&&matrix[pos.first][pos.second]>=matrix[new_x][new_y]){
                            if(visit_p[new_x][new_y]&&pacific[new_x][new_y]){
                                pacific[pos.first][pos.second]=true;
                            } 
                            if(!visit_p[new_x][new_y]){
                                dfs.push(make_pair(new_x,new_y));
                            }
                            visit_p[pos.first][pos.second]=true;
                        }
                    }
                }
            }
        }
        cout<<endl;
        for(int i=0;i<x_len;i++){
            for(int j=0;j<y_len;j++){
                cout<<pacific[i][j]<<" ";            
            }
            cout<<endl;
        }

        //cout<<dfs.empty()<<endl;

        //a
        for(int i=x_len-1;i>=0;i--){
            for(int j=y_len-1;j>=0;j--){
                if(visit_a[i][j]){
                    continue;
                }
                dfs.push(make_pair(i,j)); 
                visit_a[i][j]=true;    
                while(!dfs.empty()){
                    pos=dfs.top();
                    dfs.pop();
                    for(auto& dir:direction){
                        new_x=pos.first+dir[0];
                        new_y=pos.second+dir[1];
                        if(0<=new_x&&new_x<x_len&&0<=new_y&&new_y<y_len&&matrix[pos.first][pos.second]>=matrix[new_x][new_y]){
                            if(visit_a[new_x][new_y]&&atlantic[new_x][new_y]){
                                atlantic[pos.first][pos.second]=true;
                            }
                            if(!visit_a[new_x][new_y]){
                                dfs.push(make_pair(new_x,new_y));
                            }
                            visit_a[pos.first][pos.second]=true;
                        }
                    }
                }
            }
        }
        
        cout<<endl;
        for(int i=0;i<x_len;i++){
            for(int j=0;j<y_len;j++){
                cout<<atlantic[i][j]<<" ";            
            }
            cout<<endl;
        }
        cout<<endl;
        for(int i=0;i<x_len;i++){
            for(int j=0;j<y_len;j++){
                cout<<(atlantic[i][j]&&pacific[i][j])<<" ";
                if(atlantic[i][j]&&pacific[i][j]){
                    res.push_back({i,j});
                }
            }
            cout<<endl;
        }
        return res;
    }
};
*/
class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        int x_len=matrix.size();
        if(x_len==0){
            return matrix;
        }
        int y_len=matrix[0].size();
        vector<vector<int>> res;
        vector<vector<bool>> pacific(x_len,vector<bool>(y_len,false));
        vector<vector<bool>> atlantic(x_len,vector<bool>(y_len,false));
        for(int i=0;i<x_len;i++){
            dfs(matrix,pacific,i,0,matrix[i][0]);
            dfs(matrix,atlantic,i,y_len-1,matrix[i][y_len-1]);
        }
        for(int j=0;j<y_len;j++){
            dfs(matrix,pacific,0,j,matrix[0][j]);
            dfs(matrix,atlantic,x_len-1,j,matrix[x_len-1][j]);
        }
        for(int i=0;i<x_len;i++){
            for(int j=0;j<y_len;j++){
                if(pacific[i][j]&&atlantic[i][j]){
                    res.push_back({i,j});
                }
            }
        }
        return res;
    }

private:
    vector<vector<int>> direction{{-1,0},{1,0},{0,1},{0,-1}};
    void dfs(vector<vector<int>>& matrix,vector<vector<bool>>& visited,int i,int j,int pre){
        if(0<=i&&i<matrix.size()&&0<=j&&j<matrix[0].size()&&!visited[i][j]&&matrix[i][j]>=pre){
            visited[i][j]=true;
            for(auto& dir:direction){
                dfs(matrix,visited,i+dir[0],j+dir[1],matrix[i][j]);
            }
        }
    }
};


int main(){
    Solution s;
    //vector<vector<int>> in{{1,2,2,3,5},{3,2,3,4,4},{2,4,5,3,1},{6,7,1,4,5},{5,1,1,2,4}};
    //vector<vector<int>> in{{1,2,3},{8,9,4},{7,6,5}};
    vector<vector<int>> in{{1,2,2,3,5},{3,2,3,4,4},{2,4,5,3,1},{6,7,1,4,5},{5,1,1,2,4}};
    //{{1,1},{1,1}}
    for(int i=0;i<in.size();i++){
        for(int j=0;j<in[0].size();j++){
            cout<<in[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
    /*
    vector<vector<int>> in{{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37},
    {75,74,73,72,71,70,69,68,67,66,65,64,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38},
    {76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113},
    {151,150,149,148,147,146,145,144,143,142,141,140,139,138,137,136,135,134,133,132,131,130,129,128,127,126,125,124,123,122,121,120,119,118,117,116,115,114},
    {152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189},
    {227,226,225,224,223,222,221,220,219,218,217,216,215,214,213,212,211,210,209,208,207,206,205,204,203,202,201,200,199,198,197,196,195,194,193,192,191,190},
    {228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265},
    {303,302,301,300,299,298,297,296,295,294,293,292,291,290,289,288,287,286,285,284,283,282,281,280,279,278,277,276,275,274,273,272,271,270,269,268,267,266},
    {304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341},
    {379,378,377,376,375,374,373,372,371,370,369,368,367,366,365,364,363,362,361,360,359,358,357,356,355,354,353,352,351,350,349,348,347,346,345,344,343,342},
    {380,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395,396,397,398,399,400,401,402,403,404,405,406,407,408,409,410,411,412,413,414,415,416,417},
    {455,454,453,452,451,450,449,448,447,446,445,444,443,442,441,440,439,438,437,436,435,434,433,432,431,430,429,428,427,426,425,424,423,422,421,420,419,418},
    {456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,483,484,485,486,487,488,489,490,491,492,493},
    {531,530,529,528,527,526,525,524,523,522,521,520,519,518,517,516,515,514,513,512,511,510,509,508,507,506,505,504,503,502,501,500,499,498,497,496,495,494},
    {532,533,534,535,536,537,538,539,540,541,542,543,544,545,546,547,548,549,550,551,552,553,554,555,556,557,558,559,560,561,562,563,564,565,566,567,568,569},
    {607,606,605,604,603,602,601,600,599,598,597,596,595,594,593,592,591,590,589,588,587,586,585,584,583,582,581,580,579,578,577,576,575,574,573,572,571,570},
    {608,609,610,611,612,613,614,615,616,617,618,619,620,621,622,623,624,625,626,627,628,629,630,631,632,633,634,635,636,637,638,639,640,641,642,643,644,645},
    {683,682,681,680,679,678,677,676,675,674,673,672,671,670,669,668,667,666,665,664,663,662,661,660,659,658,657,656,655,654,653,652,651,650,649,648,647,646},
    {684,685,686,687,688,689,690,691,692,693,694,695,696,697,698,699,700,701,702,703,704,705,706,707,708,709,710,711,712,713,714,715,716,717,718,719,720,721},
    {759,758,757,756,755,754,753,752,751,750,749,748,747,746,745,744,743,742,741,740,739,738,737,736,735,734,733,732,731,730,729,728,727,726,725,724,723,722},
    {760,761,762,763,764,765,766,767,768,769,770,771,772,773,774,775,776,777,778,779,780,781,782,783,784,785,786,787,788,789,790,791,792,793,794,795,796,797},
    {835,834,833,832,831,830,829,828,827,826,825,824,823,822,821,820,819,818,817,816,815,814,813,812,811,810,809,808,807,806,805,804,803,802,801,800,799,798},
    {836,837,838,839,840,841,842,843,844,845,846,847,848,849,850,851,852,853,854,855,856,857,858,859,860,861,862,863,864,865,866,867,868,869,870,871,872,873},
    {911,910,909,908,907,906,905,904,903,902,901,900,899,898,897,896,895,894,893,892,891,890,889,888,887,886,885,884,883,882,881,880,879,878,877,876,875,874},
    {912,913,914,915,916,917,918,919,920,921,922,923,924,925,926,927,928,929,930,931,932,933,934,935,936,937,938,939,940,941,942,943,944,945,946,947,948,949},
    {987,986,985,984,983,982,981,980,979,978,977,976,975,974,973,972,971,970,969,968,967,966,965,964,963,962,961,960,959,958,957,956,955,954,953,952,951,950},
    {988,989,990,991,992,993,994,995,996,997,998,999,1000,1001,1002,1003,1004,1005,1006,1007,1008,1009,1010,1011,1012,1013,1014,1015,1016,1017,1018,1019,1020,1021,1022,1023,1024,1025},
    {1063,1062,1061,1060,1059,1058,1057,1056,1055,1054,1053,1052,1051,1050,1049,1048,1047,1046,1045,1044,1043,1042,1041,1040,1039,1038,1037,1036,1035,1034,1033,1032,1031,1030,1029,1028,1027,1026}};
    */
    vector<vector<int>> out=s.pacificAtlantic(in);
    for(int i=0;i<out.size();i++){
        cout<<"("<<out[i][0]<<","<<out[i][1]<<"):"<<in[out[i][0]][out[i][1]]<<endl;
    }
}